package exercises.newcoder.solution;

import java.util.HashMap;

/**
 * <a href="https://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf?tpId=188&&tqId=38566&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC95 数组中的最长连续子序列</a><br/>
 *
 * @author or2
 * @Description 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
 * @create 2021年08月31日 时间: 22:29
 */
public class MLS {
    /**
     * max increasing subsequence
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS(int[] arr) {
        int ans = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : arr) {
            if (!hashMap.containsKey(num)) {
//                链接左右被分割的连续字串
                Integer left = hashMap.getOrDefault(num - 1, 0);
                Integer right = hashMap.getOrDefault(num + 1, 0);
                int length = left + right + 1;
                hashMap.put(num, length);
//                更新其边界上的值(链接被分割字串时要使用到)
                hashMap.put(num - left, length);
                hashMap.put(num + right, length);
                ans = Math.max(ans, length);
            }
        }
        return ans;
    }
}
